CallMeSurprise

记 2016 兴人类俱乐部中兴捧月-软件编程比赛

发表于 | 分类于 | 阅读次数

题目介绍

这是在“2016 兴人类俱乐部中兴捧月”软件编程挑战赛中遇到的的题目之一，第二题是实现类似于“LRU”的算法，时间因素，没来的及做。

题目详情

为了进行城市规划，需要计算一个居住区的住宅项目。该居住聚集区俯视图已经制作好，并划分成n x m个网格。如果某个网格单元具有屋顶的一部分，则向其赋值1，如果是空地，则赋值0。由值为1的相邻网格单元组成的簇认定为一个单独住宅。对角放置的值为1的网格则不被视为属于同一住宅屋顶。

类Homes的方法countHomes的输入应包括一个n x m阶的二维整数数组grid。其中，n和m分别表示输入数组grid的行数和列数。该方法应该返回一个表示住宅总数目的整数。grid只包含0和1。

有用的命令：
使用length方法来计算二维数组的长度。语句：
int row = arr.length;
int col = arr[0].length;
可分别将数组arr中的行数和列数保存在row和col中。

特别要求

必须用Java语言实现此算法。需要提交完全有效的代码，而非部分正确且有效的代码。一旦提交，便无法再检查该题。所使用的JDK版本为1.7。

注：本题可以选择Java、C++等语言，此处选择Java之后才有的这个特别要求。

测试用例

测试用例1：

1
2
3
4
5
6
{
    {0,0,0,0},
    {0,1,0,0},
    {0,0,1,0},
    {0,0,0,0}
};

结果：2。

测试用例2：

1
2
3
4
5
6
7
{
    {0,0,0,0,0},
    {0,1,1,0,0},
    {0,0,1,1,0},
    {0,0,0,0,0},
    {0,0,0,0,0}
};

结果：1。

题目分析

思路整理

分析题目可知，题目可以抽象为给定一个二维数组（数组元素只包含0或1），然后查找数组中连在一起的1的区域的个数，上下左右这类直线方式算有效连接，而斜线则不算。

测试用例1可以画图示意如下：

二维数组示意图

看图可知只有2行2列和3行3列的两个数组元素符合要求。
测试用例2思路类似。

方法选择

一种穷举才能解决的问题，要么嵌套循环来求解所有的可能情况，要么观察题目形式，找到适合的解题形式，比如此题的递归。

嵌套循环需要考虑的情况略微复杂，如某层循环每次循环时可能需要重置数组变量，以及两次循环之间的循环衔接、参数统计，最是问题的是时间复杂度会达到一个很高的量级，很繁琐。

因此考虑使用递归。

最近遇到的类似的测试题最终落脚点全都是递归，如咪咕的测试（往m个桶里倒n升的水），中兴本次测试之前的模拟测试题用的是百度实习生招聘的题目（单词首尾串联问题），本题也是，各大公司好像都很默契。

递归算法

先贴代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(int i,int j,int grid[][])
{
	if(i>=0 && i<grid.length && j>=0 && j<grid[0].length)
	{
		if(grid[i][j]==1)
		{
			temp++;
			grid[i][j]=-1;
			solve(i,j+1,grid);
			solve(i+1,j,grid);
			solve(i,j-1,grid);
			solve(i-1,j,grid);
		}
	}
}

这里是采用了CSDN用户讨论中提出的一种方案（感谢），进行适当的变化。

代码算是比较简单，入参i和j标识此次递归的参数在数组的位置，grid数组是全局变量。每次遇到1的时候，temp参数则开始计数，同时被统计的1的位置设置为-1，便于下次递归。
但是这里函数返回的是某次开始递归的连续的1的个数，而不是所有的连续1的区域数量；当继续递归找不到连续的1的时候，则退出，返回本次递归中统计的本区域内1的个数。

方法有些接近最终答案，不过需要进行稍微的改进，设置一些统计条件和改变一些递归条件：如统计区域总数而不是单个区域内连续的1的个数、重置为-1的数组元素不应继续递归，以及其他小问题。选择合适的截止条件很纠结，总是差强人意，之前实战的递归算法较少，缺乏经验，所以耽误了不少时间，还好最终拿出了一套方案。

最终版本的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package  simple;
/**
 * @author Think
 * @since 2016-06-11 19:16:00
 */
public class Homes {
	public static void main(String[] args) {

		int a[][]=
        {
            {0,0,0,0},
            {0,1,0,0},
            {0,0,1,0},
            {0,0,0,0}
        };
//        int a[][]=
//        {
//            {0,0,0,0,0},
//            {0,1,1,0,0},
//            {0,0,1,1,0},
//            {0,0,0,0,0},
//            {0,0,0,0,0}
//        };

		countHomes(a);
	}
	public static int nCount=0;
	public static int temp=0;

	public static int countHomes(int grid[][]){
		int row=grid.length;
		int col=grid[0].length;

		Homes h=new Homes();

		for (int i=0;i<row;i++){
			for (int j=0;j<col;j++){
				if (grid[i][j]<1){
					if (temp!=0){
						nCount++;
						temp=0;
						continue;
					}
				}
				h.solve(i,j,grid);
			}
		}

		System.out.println(nCount);
		return nCount;
	}

	void solve(int i,int j,int grid[][])
	{
		if(i>=0 && i<grid.length && j>=0 && j<grid[0].length && grid[i][j]>=0)
		{
			if(grid[i][j]==1)
			{
				temp++;
				grid[i][j]=-1;
				solve(i,j+1,grid);
				solve(i+1,j,grid);
				solve(i,j-1,grid);
				solve(i-1,j,grid);
			}
		}
	}

}

代码不过多解释，怎么把递归函数和整体代码结合起来倒是耽误了很多的时间，其他没什么需要着重强调的。

简单注释

  1. 包simple，Homes函数，countHomes方法，需要本地实现的时候稍作修改即可。
  2. 其中静态方法以及递归不能设置成static的问题，通过new新建类的对象即可解决。

反思

系统给定的两个测试用例本地测的时候全都通过了，但是提交上去的时候测试用例2输出结果居然不对，很费解。至今没发现问题所在。所以，欢迎发现问题的同学留言指正交流。谢谢~

实践出真知，思路和方法在头脑中还算清晰，但是落地之后还是遇到不少或大或小的问题。多练手总是有好处的，mark。